COMMENT ⊗   VALID 00012 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 00002
C00005 00003	.Sec(Symbolic expressions,Symbolic expressions)
C00008 00004	.<<Examples: s-exprs not sexprs>>
C00011 00005	.GROUP
C00012 00006	.REQUIRE "PROB1.PUB" SOURCE_FILE
C00013 00007	.SS(Primitive Functions)
C00015 00008	We have two functions for traversing binary trees.  They are both →partial functions↔←
C00018 00009	.SS(Conditional Expressions,conditional expression)
C00022 00010	%3
C00025 00011	Here's an intuitive description of such a function (predicate named %3equal%*).
C00027 00012	.SS(List Notation,lists)
C00031 ENDMK
C⊗;

.SEC (LISP - a high-level mathematical language for data structures,Introduction)

Just as it is unnecessary to learn machine language to study numerical
algorithms, it is also unnecessary to learn machine language to understand
non-numerical processes.  The distinction we are making is between data-
structures and ⊗→storage structures↔←.  That is, ⊗→data structures↔← are independent
of %6how%* they are implemented on a machine.  Data structures are representations
of information chosen to exhibit certain ordering and accessibility relation-
ship between data structures.  Certainly in the real world you cannot ignore
storage structures when you are deciding upon the data structures which
will encode your problem, but the interesting aspects of representation of
information can be discussed at the level of data structures with no loss
of generality.  The mapping of data structures to storage structures is
machine dependent anyway, and consists of bit-pushing, trickery and black
magic.  A very crucial problem in data structures and algorithms is the
interplay between the representation and the algorithm:  if you pick a
frugal representation prhaps your accessing algorithms become more time
consuming or the algorithm become less general.  We will study this
interrelation carefully in this course.

If you take a course in elementary number theory or better yet recursive
function theory, you would begin with a precise description of the domain
of interest (the non-negative integers perhaps, or 0 and the successor
function) and then describe the class of functions or operations which will
be allowed in the developing theory. We will do the same.


.Sec(Symbolic expressions,Symbolic expressions)

Our primitive domain consists of objects called ⊗→atoms↔← or ⊗→atomic symbols↔←.
In computer science terminolgy they are either identifiers or ⊗→numbers↔←; i.e.
.GROUP SKIP 2;
.BEGIN TABIT1(13);
.GROUP;
<atom>\:: = <identifier>|<number>
<identifier>\:: = <letter>|<identifier><letter>|<identifier><digit>
<number>\:: = <digit>|<number><digit>
<letter>\:: =%3 A |B |C ...| Z%*
<digit>\:: = %30 |1 |2 ... |9%*
.APART;
.END;
.GROUP SKIP 2;
.BEGIN TABIT2(20,35);DOUBLE SPACE;
.GROUP;
For example:\atoms\not atoms
%3\ABC123\2a
\12\a
\A4D6\$$g
\NIL\ABD.
\T\(A . B)
%*
.APART;
.END;

Using an operator to be described later, we are able to enlarge on
this primitive domain obtaining the domain of interest for LISP functions,
that is the class of %6⊗→symbolic expressions↔←%* or %6⊗→S-expressions↔←%* or also called
%6⊗→S-exprs↔←%*.  S-exprs include as a proper subset the atoms, but S-exprs can be
constructed of other S-exprs as follows:  a left-paren followed by an
S-expr, followed by a period, followed by an S-expr, followed by a
period, followed by an S-expr, followed by a right-paren is also an S-expr.
To make everyone happy here's a BNF definition of S-expr
.TURN ON "←";

←<sexpr> :: = <atom>|%3(%*<sexpr> . <sexpr>%3) |( )%*

.TURN OFF "←";
We added "%3( )%*" as an S-expr for a reason which will become clear later.


.<<Examples: s-exprs not sexprs>>
.BEGIN TABIT2(20,40);
.GROUP;
Examples:\S-exprs\not S-exprs
%3
\A\A . B
\(A . B)\(A . B . C)
\(((A.B) .C) . (A.B))\((A . B)))
%*
.APART;
.END;
.SS(Binary trees)
Non-atomic sexprs are also called %6⊗→dotted-pairs↔←%*.  S-exprs have a natural
interpretation as %6⊗→binary trees↔←%*.  A binary tree is a branching structure 
consisting of a single root node and perhaps a collection of terminal
and non-terminal nodes.  From non-terminal nodes we sprout exactly two
branches; no branches are grown from the terminal nodes.  And most
important:  there are no intersecting branches.  We will talk about more
general structures later (called list-structures or directed graphs).
.GROUP SKIP 2;
.GROUP;
Here are some binary tres:

%3
.BEGIN NOFILL;

					.		   
		       			A                
	                 			    	A       
	 

	1      2	 					B      NIL


		A   	D     E



		B    C

.END
.APART;
%1
Perhaps you can see how to interpret S-exprs now.  The atoms are
interpreted as terminal nodes;  and since non-atomic S-exprs always
have two branches (oops, two sub-expressions) we can write the first
sub-expression as the left branch of a binary tree and the second sub-
expression as the right branch.  
.GROUP SKIP 2;
.GROUP;
For example:

%3
.BEGIN VERBATIM;
	(A . B)				(A . (B . C))



				       A   

	 A  B				 
					B    C


.APART;

.GROUP;





	((A . B) . C)			(A . (B . NIL))





	  	C			A  


     A      B				    B      NIL

.APART;
.END
%1
Other representations of binary trees which will be more suggestive when
we talk about implementation of LISP are:
%3
.GROUP
.BEGIN VERBATIM

(A . (B . C))



 ≡        A             ≡                                 ≡ 

	                          A            B     C 


	      B    C  						A




								   B        C

.END;
.APART

%6Note that the translation process is inherently recursive.
%1
.REQUIRE "PROB1.PUB" SOURCE_FILE;
.SS(Primitive Functions)
%1
So much for the domain of objects;  what we need now are some functions
or operators to perform oprations on the domain.  First such function is the
⊗→%3cons%*↔← (construct) function wwich is used to generate s-exprs from less
complicated s-exprs.  %3cons%* is a ⊗→total function↔←, that is it is defined for all
sexpr arguments. It is a function of two arguments and has as value a
new sexpr interpreted as a binary tree with left branch as the first argument
and with right branch, the second argument.  For example:
 
.BEGIN CENTERIT;
←%3cons[A; B] = (A . B)

←cons[(A . B); C] = ((A . B) .C)
.END;
%1

.GROUP SKIP 2;
We have two functions for traversing binary trees.  They are both ⊗→partial functions↔←;
that is they are (unary) functions which are undefined for atomic arguments.
⊗→%3car%*↔← returns as value the first subexpression of its (composite) argument; ⊗→%3cdr%*↔← 
(pronounced could-er) returns as value the second sub-expression of its
argument.  For example:
.GROUP SKIP 2;
.BEGIN INDENT 10; TABS 30;TURN ON "\,←";NOFILL;
.GROUP;
%3car[(A . B)] = A\car[A] %*is undefined.
%3cdr[(A . B)] = B\cdr[A(A . (B . C))] = (B . C)
←car[((A . B) . C)] = (A . B)
%*
.APART;
.END;
.GROUP SKIP 1;
.GROUP;
As with most mathematical theories, we will allow ⊗→functional composition↔←.
.BEGIN CENTERIT;
%3
←car[cdr[(A . (B . C))]] = B = cdr[cdr[(A . (C . B))]]
←car[cons[x;y]] = x     cdr[cons[x;y]] = y .
%*
.END;
.APART

Notice that in the last two examples we have introduced variables (over
S-exprs).  In the sequel lower-case letters (or lower-case identifiers) will be
used freely as (sexpr) variables.  So for example %3Y%* is an atom; %3x%* is a variable
The composition of many %3car%* and %3cdr%* functions occurs so frequently that an
abbreviation has been developed.  
.GROUP SKIP 2;
.BEGIN CENTERIT;DOUBLE SPACE;
.GROUP;
For example:
%3
←cadr[x] ≡ car[cdr[x]]
←caddr[x] ≡ car[cdr[cdr[x]]]
←cdar[x] ≡ cdr[car[x]]
%*
.end;

These compositions are also called ⊗→%3car-cdr %2chains%1↔←, and are useful in
traversing binary trees.

.SS(Conditional Expressions,conditional expression)

We cannot generate a very exciting theory based simply on %3car, cdr,%* and %3cons
%*
with functional composition. Before we can write reasonably interesting 
algorithms we must have some way of performing conditional actions;
an IF-THEN-ELSE facility if you wish.  To do this we need ⊗→predicates↔←:  functions
returning a value representing truth or falsity.  Since our functions
return Sexprs as values we must represent truth and falsity as Sexprs.
We will take the atoms ⊗→%3T%*↔← and ⊗→%3NIL%*↔← to represent ⊗→true↔← and ⊗→false↔←, respectively.
Now two predicates. The first is a total predicate named ⊗→%3atom%*↔←.  It is a predicate
of one argument returning, %3T%* or %3NIL%* depending on whether or not that
argument is atomic.
.BEGIN CENTERIT;
.GROUP
%3
←atom[A] ≡ atom[NIL] = T
←atom[atom[A]] = T = atom[atom[(A . B)]]
%*
.APART
.END

The second primtive predicate is named ⊗→%3eq%*↔←.  It is a binary predicate defined
only if its arguments are both atomic.  It returns %3T%* if the arguments are the
same atom; it returns %3NIL%* otherwise.
.BEGIN CENTERIT;
%3
.GROUP SKIP 1;
.GROUP
←eq [A;A] = T			eq [A;B] = NIL
←eq [(A . B); A] %* is undefined, as is  %3eq [(A . B);(A . B)]
←eq [eq [A;B];eq [C;D]] = T
%*
.APART;
.END

The IF-THEN-ELSE operation in LISP is called the conditional expression.  It
is written:
.BEGIN CENTERIT;
%3
←[p%41%* → e%41%*; p%42%* → e%42%*  ... ; p%4n%*  → e%4n%*]
%1
.END

The meaning (or semantics) of conditionals is:  Each %3p%4i%1 is a predicate; 
each %3e%4i%1
is an expression.  We evaluate the %3p%4i%1 's from left to right, finding the first
which returns value %3T%*.  When we find such a %3p%4i%1 , we evaluate the corresponding
%3e%4i%1.  The value of the conditional expression the value returned by %3e%4%1; if none
of the %3p%4i%1's are true then the conditional expression is undefined.  The
conditional expression is also undefined if we come across a %3p%4i%1
which is undefined.  
.BEGIN CENTERIT;
.GROUP;
Examples:

%3
←[atom [A] → B; eq [A;(A . B)] → C] = B
←[eq [A;(A . B)] → C; atom [A] → B] is undefined
←[atom [(A . B)] → B; eq [A ; B] → C; eq [car[(A . B)]; cdr[(B . A)]] → E] = E
%1
.APART
.END


In applications of conditional expressions it is often convenient to be
assured that the conditional always is defined.  To make sure that at least one of
the %3p%4i%1's is true we can pick a predicate for %3p%4n%1, (the last predicate in the 
conditional) which is always true.  You can think of lots of predicates which
are always true ( for example, %3eq [1;1]%* ).  A natural predicate is the
constant predicate, %3T%*.  Thus:
.GROUP

.BEGIN CENTERIT;

%3
←[p%41%*  → e%41%*; T → e%42%*]
%1
.END
can be read:  If %3p%41%1  is true then  %3e%41%1  else %3e%42%1.  (or otherwise %3e%42%1)

.APART;
A word to the wise.  It doesn't seem like you can do much damage with such
a limited collection of operations.  %6Do not be deceived!%*  In elementary number
theory all you have is zero and some simple functions, and elementary number theory
is far from elementary.

For example: our predicate %3eq%* is defined only for atomic arguments.  We would like
to be able to test for equality of arbitrary sexprs.  For example, we would
like to define a predicate, ⊗→%3equal%*↔←, such that:
.GROUP SKIP 1;
.GROUP
.BEGIN CENTERIT;
%3
←equal [(A . B);(A . B)] = T = equal [A,A]
←equal [(A . B);(B . A)] = NIL 
←equal [(A . (B . C));(A . (B . C))] = T

%1
.END
.APART
Here's an intuitive description of such a function (predicate named %3equal%*).

1.  if both arguments are atomic then see what %3eq%* says about them
(are they "%3eq%*").  We make sure that they are both atomic by using %3atom%*
and a conditional expression.

2.  If one is atomic and the other is not they can't be equal s-exprs.

3.  Otherwise both are non-atomic sexprs.  Both have two sub-expressions.

Look at both first subexpressions.  If the first sub-expressions are not
equal then certainly the initial expressions cannot hope to be equal.  
However, if the first subexpressions are equal then the question of
whether or not the initial expressions are equal depends on the
equality ( or non-equality) of the second subexpressions.  Thus the
following definition:
.GROUP
%3
.BEGIN TABIT2(19,30);

equal[x,y] <=\[atom[x] → [atom[y] → eq [x;y]
\\ T→ NIL];
\ atom[y] → NIL;
\ equal [car[x];car[y]] → equal[cdr[x];cdr[y]];
\ T → NIL]

.END
.APART
%1
.REQUIRE "PROB2.PUB" SOURCE_FILE;
.REQUIRE "PROB3.PUB" SOURCE_FILE;
.SS(List Notation,lists)

In many applications of LISP it will be very convenient to represent
sequences.  E.g. %3(x%41%*, x%42%*, x%43%*)%1.  We will allow sequences to have
sub-sequences (to an arbitrary depth) e.g. %3(A,(B,C),D,(E,B))%*.  The obvious
question is how to represent sequences as Sexprs.  Since sequences can be of
arbitrary length any representation must include an unambiguous way of
determining the end of such a sequence.
.GROUP
The choice we make is represented graphically as follows:
%3
.BEGIN VERBATIM


	                                             ≡ (X  . (Y  . (Z  . NIL)))

X		Y		Z      NIL

.END
.APART
%1

Note that we can determine the end of the sequence using the predicate:

.BEGIN CENTERIT;
%3
←endofseq[x] = [atom[x] → eq[x,NIL]; T → NIL]
%1
.END

That is the right-hand branch in any binary tree representing a sequence
will always point to the rest of the sequence or will be the atom %3NIL%*.  It
is not by accident that the atom %3NIL%* is used for falsity and the termination
symbol for sequences.  You should become fluent in translating between
sexpr-notation and sequence notation.

In standard Computer Science terminology sequences are called lists, thus we
will refer usually to ⊗→list-notation↔←, list terminator, etc.  You should also
become fluent in applying our basic functions to lists without having to
translate back to sexpr-notation.

A final point:  what about the empty sequence or empty list? Looking at the
graphical interpretation of a sequence it appears natural to take ⊗→%3NIL%*↔← as
the ⊗→empty list↔← since after you have removed all the elements from the list,
%3NIL%*, the list terminator is all that is left.  Also from the standpoint of
sequence notation, the empty sequence is represented as:  "⊗→%3( )%*↔←".  To be
consistent, then, we will define %3( )%* to be the same as the atom %3NIL%*.  And
a notational point:  in graphical notation it is often convenient to write
.GROUP
.BEGIN TABIT2(10,30);

\\as                  .  

\       %3NIL%*
.END
.APART
%1
.BEGIN TURN ON "←";TABIT3(20,30,40);
.GROUP
Thus, for example:

←%3(A,(B,C),D)%* is:



%3
\A\\    D



\\   B\   C

%1
or:
%3

←A








←B    C    NIL     D    NIL 
%1

.END
.APART
Finally in list-notation, the commas can be replaced by spaces.
.BEGIN CENTERIT;
%3

←e.g. (A,(B,C),D) ≡ (A(B C)D).
%1
.END
Note:  the "dots" in dot-notation are never optional.

.REQUIRE "PROB4.PUB" SOURCE_FILE;